public class test {

        public static void main(String[] args) {
            int[] arr = {9, 5, 7, 1, 3, 8, 4, 2, 6};

            System.out.println("排序前的数组：");
            printArray(arr);

            quickSort(arr, 0, arr.length - 1);

            System.out.println("\n排序后的数组：");
            printArray(arr);
        }

        // 快速排序的主方法
        public static void quickSort(int[] arr, int low, int high) {
            if (low < high) {
                int pivotIndex = partition(arr, low, high);
                quickSort(arr, low, pivotIndex - 1);
                quickSort(arr, pivotIndex + 1, high);
            }
        }

        // 分区方法，选择最后一个元素作为基准
        private static int partition(int[] arr, int low, int high) {
            int pivot = arr[high];
            int i = low - 1;

            for (int j = low; j < high; j++) {
                if (arr[j] <= pivot) {
                    i++;
                    swap(arr, i, j);
                }
            }

            swap(arr, i + 1, high);
            return i + 1;
        }

        // 交换数组中两个元素的位置
        private static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        // 辅助方法：打印数组
        private static void printArray(int[] arr) {
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
        }

}
